/**
 * Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,3,2].
 */
package com.xinpan.exercise;

import java.util.ArrayList;

public class InorderTraversal 
{
    public ArrayList<Integer> inorderTraversal(TreeNode root) 
    {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> resList = new ArrayList<Integer>();
        
        if(root == null)
            return resList;
        
        resList = inorderTraversal(root.left);
        
        resList.add(root.val);
        resList.addAll(inorderTraversal(root.right));
        
        return resList;
    }
    
    class TreeNode {
    	 int val;
    	 TreeNode left;
    	 TreeNode right;
    	 TreeNode(int x) { val = x; }
    }
}
